Container adaptors in C++ STL¶
La standard template library (STL) met en oeuvre les types de données abstraits vus dans ce chapitre sous forme de container adaptors. Ils
- utilisent un des sequence container vus précédemment pour gérer les éléments
- fournissent un interface indépendant du conteneur utilisé
La STL en fournit trois
| Classe | Description |
|---|---|
std::stack<T> |
pile Last In First Out |
std::queue<T> |
queue First In First Out |
std::priority_queue<T> |
queue de priorité |
std::stack<T, Container>¶
fournit les méthodes essentielles au TDA Pile.
| Méthode | Description |
|---|---|
empty() |
le conteneur est-il vide? |
size() |
nombre d'éléments |
push(t) emplace(t) |
ajoute un élément au sommet |
top() |
référence à l'élément au sommet |
pop() |
supprime l'élément au sommet |
Notons que top() et pop() sont séparés, ce qui permet de donner de bonnes garanties en cas d'exception.
En interne, l'adapteur stack utilise le type Container spécifié en paramètre générique. Par défaut, il utilise std::deque<T>. On peut choisir tout conteneur qui fournit les méthodes
empty(),size()back(),push_back(t)etpop_back()
On peut donc utiliser soit une classe personalisée, soit les conteneurs
std::vector<T>std::list<T>std::deque<T>
Bien qu'une liste simplement chainée puisse normalement servir pour mettre en oeuvre une pile, std::stack<T> ne permet pas d'utiliser std::forward_list<T>, les opérations se faisant du "mauvais" côté pour l'adapteur: front()
std::queue<T, Container>¶
fournit les méthodes essentielles au TDA Queue.
| Méthode | Description |
|---|---|
empty() |
le conteneur est-il vide? |
size() |
nombre d'éléments |
push(t) emplace(t) |
insère un élément |
front() |
référence au prochain élément |
back() |
référence au dernier élément |
pop() |
supprime l'élément suivant |
Notons que front() et pop() sont séparés, ce qui permet de donner de bonnes garanties en cas d'exception.
En interne, l'adapteur queue utilise le type Container spécifié en paramètre générique. Par défaut, il utilise std::deque<T>. On peut choisir tout conteneur qui fournit les méthodes
empty(),size()back(),push_back(t)front(),pop_front()
On peut donc utiliser soit une classe personalisée, soit les conteneurs
std::list<T>std::deque<T>
Bien qu'une liste simplement chainée qui se souviendrait du maillon de queue pourrait normalement servir pour mettre en oeuvre une queue, std::forward_list<T> ne peut-être utilisée puisqu'elle ne fournit aucune méthode du coté back().
std::priority_queue<T, Container, Compare>¶
fournit les méthodes essentielles au TDA Queue de priorité.
| Méthode | Description |
|---|---|
empty() |
le conteneur est-il vide? |
size() |
nombre d'éléments |
push(t) emplace(t) |
insère un élément |
front() |
référence à l'élément le plus prioritaire |
pop() |
supprime l'élément le plus prioritaire |
Notons que front() et pop() sont séparés, ce qui permet de donner de bonnes garanties en cas d'exception.
En interne, l'adapteur priority_queue utilise le type Container spécifié en paramètre générique. Par défaut, il utilise std::vector<T>. On peut choisir tout conteneur qui fournit
empty(),size()back(),push_back(t),pop_back()- un random access iterator
En effet, les données sont organisées sous forme d'un tas (heap), ce qui requiert un accès indexé. On peut donc utiliser soit une classe personalisée, soit les conteneurs
std::vector<T>std::deque<T>
|
© Olivier Cuisenaire, 2018 |